package com.kongge.algorithm.demo;

/**
 * 输入一个整数数组，判断该数组是不是某个二叉搜索树的后续遍历的结果。
 * 二叉搜索树，根节点的左叶子节点比根节点小，右叶子节点比根节点大。
 * 后续遍历，最后面那个是根节点，前半部分的值比它小，后边部分比它大。
 * @author gaoshiqi
 *
 */
public class BinarySearchTreeDemo implements IAlgorithm {

	public void execute() {
		int[] arr = {5, 7, 6, 9, 11, 10, 8};
//		int[] arr = {7, 4, 6, 5};
		/*BinarySearchTree<Comparable<Integer>> binarySearchTree = new BinarySearchTree<Comparable<Integer>>();
		for (int i = 0; i < arr.length; i++) {
			binarySearchTree.add(arr[i]);
		}
		List<Comparable<Integer>> resultList = binarySearchTree.traveseTreeByType(ITree.TRAVESE_TYPE_MID);
		for (int i = 0; i < resultList.size(); i++) {
			System.out.println(" " + resultList.get(i));
		}*/
		boolean result = verifySquenceOfBST(arr, 0, arr.length - 1);
		System.out.println("result is " + result);
	}
	
	private boolean verifySquenceOfBST(int[] sequence, int left, int right) {
		if (sequence == null || sequence.length == 0 || left < 0 || right >= sequence.length || left > right) {
			return false;
		}
		int rootValue = sequence[right];
		int leftIndex = left;
		for ( ; leftIndex < right; leftIndex++) {
			if (sequence[leftIndex] > rootValue) {
				break;
			}
		}
		int rightIndex = leftIndex;
		for ( ; rightIndex < right; rightIndex ++) {
			if (sequence[rightIndex] < rootValue) {
				return false;
			}
		}
		boolean leftIsSqueceOfBST = true;
		if (leftIndex > left) {
			leftIsSqueceOfBST = verifySquenceOfBST(sequence, left, leftIndex - 1);
		}
		boolean rightIsSqueceOfBST = true;
		if (leftIndex < right - 1) {
			rightIsSqueceOfBST = verifySquenceOfBST(sequence, leftIndex, right - 1);
		}
		return leftIsSqueceOfBST && rightIsSqueceOfBST;
	}

}
